//给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 
//
// 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 
//
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
// 和 "192.168@1.1" 是 无效的 IP 地址。 
//
// 
//
// 示例 1： 
//
// 输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
// 
//
// 示例 2： 
//
// 输入：s = "0000"
//输出：["0.0.0.0"]
// 
//
// 示例 3： 
//
// 输入：s = "1111"
//输出：["1.1.1.1"]
// 
//
// 示例 4： 
//
// 输入：s = "010010"
//输出：["0.10.0.10","0.100.1.0"]
// 
//
// 示例 5： 
//
// 输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3000 
// s 仅由数字组成 
// 
// Related Topics 字符串 回溯算法 
// 👍 403 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

//Java：复原IP地址
public class P93RestoreIpAddresses {

    /**
     * 思路： 回溯算法，循环k = 0 1 2 ，然后判断 substring(i,i+k+1) 的结果是否符合，不符合的话回溯，符合的话继续
     * <p>
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 81.43% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 62.95% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<String> list = new ArrayList<>();

        public List<String> restoreIpAddresses(String s) {
            if (s.length() >= 4) {
                dfs(0, s, new Stack<>());
            }
            return list;
        }

        /**
         * 描述： 回溯
         *
         * @param i     当前待遍历下标
         * @param s     目标字符串
         * @param stack 符合的结果[路径]
         * @return "void"
         * @date: 2020/9/3 16:36
         */
        private void dfs(int i, String s, Stack<String> stack) {
            if (!stack.isEmpty()) {
                String str = stack.peek();
                int num = Integer.parseInt(str);
                // 不在 0-255
                if (num < 0 || num > 255) {
                    return;
                }
                // 以0开头
                if (str.length() > 1 && str.charAt(0) == '0') {
                    return;
                }
            }

            // 栈四个满了，得判断是否s有剩余
            if (stack.size() == 4) {
                // 符合要求 加
                if (i == s.length()) {
                    Iterator<String> it = stack.iterator();
                    StringBuilder sb = new StringBuilder("");
                    while (it.hasNext()) {
                        String s1 = it.next();
                        sb.append(s1);
                        if (it.hasNext()) {
                            sb.append(".");
                        }
                    }
                    list.add(sb.toString());
                }
                return;
            }


            for (int k = 0; k < 3; k++) {
                int end = i + k + 1;
                if (end > s.length()) {
                    break;
                }
                stack.add(s.substring(i, end));
                dfs(end, s, stack);
                stack.pop();
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P93RestoreIpAddresses().new Solution();
        System.out.println(solution.restoreIpAddresses("000999"));
        // TO TEST
    }

}